#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    int height;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

int getHeight(TreeNode *node) //写成函数更易理解
{
    return node ? node->height : 0;
}

int max (int a, int b) {
    return a > b ? a : b;
}
/*
        1  root node **root改                    
         \                                      
          2 tmp(node->lchild)
           \
            3 
*/
//注意:
//LL RR
//LR = RR(root->lchild) + LL(root); 可以加两个空气节点理解
//RL = LL(root->rchild) + RR(root);
void rrRotation(TreeNode *node, TreeNode **root) 
{
    TreeNode *temp = node->rchild;//记录node->rchild 便于之后改变*root
    node->rchild = temp->lchild; //如果tmp有lchild
    temp->lchild = node;
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
    *root = temp;
}

void llRotation(TreeNode *node, TreeNode **root) 
{
    TreeNode *temp = node->lchild;//记录node->rchild 便于之后改变*root
    node->lchild = temp->rchild; //如果tmp有lchild
    temp->rchild = node;
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
    *root = temp;
}

//创建即插入
void avlInsert(TreeNode **T, int data) 
{   //do something
    if (*T == NULL) {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = data;
        (*T)->height = 0;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
    } else if (data < (*T)->data) {
        avlInsert(&((*T)->lchild), data);//先插入在判断是LR还是LL
        int lHeight = getHeight((*T)->lchild);
        int rHeight = getHeight((*T)->rchild);
        if (lHeight - rHeight == 2) {
            if (data < (*T)->lchild->data) {
                //LL
                llRotation(*T, T);
            } else {
                //LR
                rrRotation((*T)->lchild, &((*T)->lchild));
                llRotation(*T, T);
            }
        }
    } else if (data > (*T)->data) {     //此处排除==的情况
        avlInsert(&((*T)->rchild), data);
        int lHeight = getHeight((*T)->lchild);
        int rHeight = getHeight((*T)->rchild);
        if (rHeight - lHeight == 2) {
            if (data > (*T)->rchild->data) {
                //RR
                rrRotation(*T, T);
            } else {
                //RL
                llRotation((*T)->rchild, &((*T)->rchild));
                rrRotation(*T, T);
            }
        }
    }
    //调节高度
    (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
}

void preOrder(TreeNode *T) 
{
    if (T) {
        printf("%d ", T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

int main(int argc, char *argv[])
{
    TreeNode *T = NULL;
    int nums[] = {8, 7, 9, 5, 6};
    int len = sizeof(nums) / sizeof(nums[0]);
    for (int i = 0; i < len; i++) {
        avlInsert(&T, nums[i]);
    }
    preOrder(T);
    return 0;
}